/**
 * 1254. 统计封闭岛屿的数目
 * https://leetcode-cn.com/problems/number-of-closed-islands/
 */
public class Solutions_1254 {
    public static void main(String[] args) {
        int[][] grid = {{1, 1, 1, 1, 1, 1, 1, 0},
                        {1, 0, 0, 0, 0, 1, 1, 0},
                        {1, 0, 1, 0, 1, 1, 1, 0},
                        {1, 0, 0, 0, 0, 1, 0, 1},
                        {1, 1, 1, 1, 1, 1, 1, 0}};  // output: 2

//        int[][] grid = {{0, 0, 1, 0, 0},
//                        {0, 1, 0, 1, 0},
//                        {0, 1, 1, 1, 0}};  // output: 1

//        int[][] grid = {{1, 1, 1, 1, 1, 1, 1},
//                        {1, 0, 0, 0, 0, 0, 1},
//                        {1, 0, 1, 1, 1, 0, 1},
//                        {1, 0, 1, 0, 1, 0, 1},
//                        {1, 0, 1, 1, 1, 0, 1},
//                        {1, 0, 0, 0, 0, 0, 1},
//                        {1, 1, 1, 1, 1, 1, 1}};  // output: 2

//        int[][] grid = {{0, 0, 1, 1, 0, 1, 0, 0, 1, 0},
//                        {1, 1, 0, 1, 1, 0, 1, 1, 1, 0},
//                        {1, 0, 1, 1, 1, 0, 0, 1, 1, 0},
//                        {0, 1, 1, 0, 0, 0, 0, 1, 0, 1},
//                        {0, 0, 0, 0, 0, 0, 1, 1, 1, 0},
//                        {0, 1, 0, 1, 0, 1, 0, 1, 1, 1},
//                        {1, 0, 1, 0, 1, 1, 0, 0, 0, 1},
//                        {1, 1, 1, 1, 1, 1, 0, 0, 0, 0},
//                        {1, 1, 1, 0, 0, 1, 0, 1, 0, 1},
//                        {1, 1, 1, 0, 1, 1, 0, 1, 1, 0}};  // output: 5

        int result = closedIsland(grid);
        System.out.println(result);
    }

    private static int res = 0, row = 0, col = 0;
    public static int closedIsland(int[][] grid) {
        res = 0;
        row = grid.length;
        col = grid[0].length;
        // 第一行和最后一行，第一列和最后一列，不遍历
        for (int i = 1; i < row - 1; i++) {
            for (int j = 1; j < col - 1; j++) {
                if (grid[i][j] == 0 && dfs(grid, i, j)) {
                    res ++;
                }
            }
        }
        return res;
    }

    public static boolean dfs(int[][] grid, int i, int j) {
        if (check(grid, i, j)) {
            // 结束条件：能够到达边界，并且边界上元素是 0，说明不是封闭的
            return false;
        }
        if (grid[i][j] == 0) {
            // 标记状态，grid[i][j] 不再表示一座岛屿
            grid[i][j] = 2;
            boolean upRes = dfs(grid, i - 1, j);
            // 为什么不提前返回呢？因为需要将这一座岛屿全部标记为非岛屿
            boolean downRes = dfs(grid,i + 1, j);
            boolean leftRes = dfs(grid, i, j - 1);
            boolean rightRes = dfs(grid, i, j + 1);
            // 上、下、左、右四个方向都被水域包围
            return upRes && downRes && leftRes && rightRes;
        }
        return true;
    }

    public static boolean check(int[][] grid, int i, int j) {
        return (i <= 0 || j <= 0 || i >= row - 1 || j >= col - 1) && grid[i][j] == 0;
    }
}
